package com.example.algorithm.dynamicprogramming;

/**
 * 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：
 *  若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
 *  或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
 *  也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
 *  返回 A 的最大湍流子数组的长度。
 *
 *  示例 1：
 *  输入：[9,4,2,10,7,8,8,1,9]
 * 输出：5
 * 解释：(A[1] > A[2] < A[3] > A[4] < A[5])
 *
 *  示例 2：
 *  输入：[4,8,12,16]
 * 输出：2
 *
 *  示例 3：
 *  输入：[100]
 * 输出：1
 */
public class Leetcode978_MaxTurbulenceSize {
    public static void main(String[] args) {
        int[] nums = {9, 4, 2, 10, 7, 8, 8, 1, 9};
        System.out.println(new Solution().maxTurbulenceSize(nums));

    }

    static class Solution {
        /**
         * 双指针法
         * 遍历一次输入数组，记录上一个位置数值的变化是增加还是减少，只要上一个位置数值的变化与当前不同，
         * 当前得到湍流子数组的长度就加 11。在遍历的过程中，记录所有的湍流子数组的长度的最大值。
         *
         * @param arr
         * @return
         */
        public int maxTurbulenceSize2(int[] arr) {
            if (arr == null || arr.length < 2) {
                return arr.length;
            }
            int left = 0;
            int right = 1;
            boolean preState = false;
            int res = 1;
            while (right < arr.length) {
                boolean curState = arr[right - 1] < arr[right];
                if (curState == preState) {
                    left = right - 1;
                }

                if (arr[right] == arr[right - 1])
                    left = right;

                right++;

                res = Math.max(res, right - left);
                preState = curState;
            }

            return res;
        }

        /**
         * 动态规划:
         * 元素的值的变化「减少」和「增加」交替出现，且相邻元素的值不能相等,且子数组是输入数组里 连续 的一部分
         *
         * 原问题与子问题:
         *    1.子问题:求解前i个元素的最长湍流子数组的长度
         *
         *    2.设计状态:
         *      两个状态:分别表示以 i 结尾的在增长和降低的最长湍流子数组长度。
         *      increased[i]:以 arr[i] 结尾，并且 arr[i - 1] < arr[i] 的湍流子数组的长度
         *      decreased[i]:以arr[i] 结尾，并且 arr[i - 1]  > arr[i] 的湍流子数组的长度
         *
         *    3.状态转移方程:
         *       if (arr[i - 1] < arr[i])
         *          increased[i] = decreased[i - 1] + 1
         *
         *        if (arr[i - 1] > arr[i])
         *          decreased[i] = increased[i - 1] + 1
         *
         *        if (arr[i - 1] == arr[i])  decreased[i] = increased[i] = 1
         *       目标值 = max(decreased[i], increased[j])
         *    4.边界值: increased[0]=decreased[0]=1
         * @param arr
         * @return
         */
        public int maxTurbulenceSize1(int[] arr) {
            if (arr == null || arr.length < 2) {
                return arr.length;
            }
            int[] increased = new int[arr.length];
            int[] decreased = new int[arr.length];
            decreased[0] = increased[0] = 1; //初始化边界值

            int res = 1;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i - 1] > arr[i]) {
                    decreased[i] = increased[i - 1] + 1;
                    increased[i] = 1;
                }

                if (arr[i - 1] < arr[i]) {
                    increased[i] = decreased[i - 1] + 1;
                    decreased[i] = 1;
                }

                if (arr[i - 1] == arr[i]) {
                    decreased[i] = 1;
                    increased[i] = 1;
                }
                res = Math.max(res, Math.max(increased[i], decreased[i]));
            }
            return res;
        }

        public int maxTurbulenceSize(int[] arr) {
            return maxTurbulenceSize2(arr);
        }
    }
}
